package pers.tz.题目.排序;

import pers.tz.common.SortUtils;

/**
 * 插入排序是不稳定的排序算法，最好情况时间复杂度是n，最坏的情况是n^2
 * @Author irony
 * @Date 2024-03-09
 */
public class 插入排序 {
    public static void main(String[] args) {
        int[] ints = SortUtils.generateRandomArray(100000);
        SortUtils.printArrayTime(() -> insertSort(ints), ints, false);
    }

    /**
     * 插入排序
     */
    private static void insertSort(int[] ints) {
        for (int i = 1; i < ints.length; i++) {
            int newNumberIndex = i;

            while (newNumberIndex - 1 >= 0 && ints[newNumberIndex - 1] > ints[newNumberIndex]) {
                int temp = ints[newNumberIndex];
                ints[newNumberIndex] = ints[newNumberIndex - 1];
                ints[newNumberIndex - 1] = temp;

                newNumberIndex--;
            }
        }
    }
}
